翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Nesting problem (geometric optimization) ： ウィキペディア英語版 Cutting stock problem In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem in mathematics that arises from applications in industry. In terms of computational complexity, the problem is an NP-complete problem reducible to the knapsack problem. The problem can be formulated as an integer linear programming problem. == Formulation and solution approaches == The standard formulation for the cutting-stock problem (but not the only one) starts with a list of ''m'' orders, each requiring $q\_j,\; j\; =\; 1,\backslash ldots,m$ pieces. We then construct a list of all possible combinations of cuts (often called "patterns"), associating with each pattern a positive integer variable $x\_i$ representing how long each pattern is to be used. The linear integer program is then: :$\backslash min\backslash sum\_^n\; c\_i\; x\_i$ :$\backslash text\backslash sum\_^n\; a\_\; x\_i\; \backslash ge\; q\_j,\; \backslash quad\; \backslash quad\; \backslash forall\; j=1,\backslash dots,m$ :$x\_i\; \backslash ge\; 0$, integer where $a\_$ is the number of times order $j$ appears in pattern $i$ and $c\_i$ is the cost (often the waste) of pattern $i$. The precise nature of the quantity constraints can lead to subtly different mathematical characteristics. The above formulation's quantity constraints are minimum constraints (at least the given amount of each order must be produced, but possibly more). When $c\_i=1$ the objective minimises the number of utilised master items and, if the constraint for the quantity to be produced is replaced by equality, it is called the bin packing problem. The most general formulation has two-sided constraints (and in this case a minimum-waste solution may consume more than the minimum number of master items): :$q\_j\; \backslash le\; \backslash sum\_^n\; a\_\; x\_i\; \backslash le\; Q\_j,\; \backslash quad\; \backslash quad\; \backslash forall\; j=1,\backslash dots,m$ This formulation applies not just to one-dimensional problems. Many variations are possible, including one where the objective is not to minimise the waste, but to maximise the total value of the produced items, allowing each order to have a different value. In general, the number of possible patterns grows exponentially as a function of ''m'', the number of orders. As the number of orders increases, it may therefore become impractical to enumerate the possible cutting patterns. An alternative approach uses delayed column-generation. This method solves the cutting-stock problem by starting with just a few patterns. It generates additional patterns when they are needed. For the one-dimensional case, the new patterns are introduced by solving an auxiliary optimization problem called the knapsack problem, using dual variable information from the linear program. The knapsack problem has well-known methods to solve it, such as branch and bound and dynamic programming. The Delayed Column Generation method can be much more efficient than the original approach, particularly as the size of the problem grows. The column generation approach as applied to the cutting stock problem was pioneered by Gilmore and Gomory in a series of papers published in the 1960s.〔Gilmore P. C., R. E. Gomory (1961). ''A linear programming approach to the cutting-stock problem''. Operations Research 9: 849-859〕〔Gilmore P. C., R. E. Gomory (1963). ''A linear programming approach to the cutting-stock problem - Part II''. Operations Research 11: 863-888〕 Gilmore and Gomory showed that this approach is guaranteed to converge to the (fractional) optimal solution, without needing to enumerate all the possible patterns in advance. A limitation of the original Gilmore and Gomory method is that it does not handle integrality, so the solution may contain fractions, e.g. a particular pattern should be produced 3.67 times. Rounding to the nearest integer often does not work, in the sense that it may lead to a sub-optimal solution and/or under- or over-production of some of the orders (and possible infeasibility in the presence of two-sided demand constraints). This limitation is overcome in modern algorithms, which can solve to optimality (in the sense of finding solutions with minimum waste) very large instances of the problem (generally larger than encountered in practice〔Goulimis C (1990). ''Optimal solutions for the cutting stock problem''. European Journal of Operational Research 44: 197-208〕〔de Carvalho V (1998). ''Exact solution of cutting stock problems using column generation and branch-and-bound''. International Transactions in Operational Research 5: 35–44〕). The cutting-stock problem is often highly degenerate, in that multiple solutions with the same waste are possible. This degeneracy arises because it is possible to move items around, creating new patterns, without affecting the waste. This gives rise to a whole collection of related problems which are concerned with some other criterion, such as the following: * The minimum pattern count problem: to find a minimum-pattern-count solution amongst the minimum-waste solutions. This is a very hard problem, even when the waste is known.〔S. Umetani, M. Yagiura, and T. Ibaraki (2003). ''One dimensional cutting stock problem to minimize the number of different patterns''. European Journal of Operational Research 146, 388–402〕〔A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo (1996). ''Setup minimizing conditions in the trim loss problem''. European Journal of Operational Research 95:631-640〕〔C. McDiarmid (1999). ''Pattern Minimisation in Cutting Stock Problems''. Discrete Applied Mathematics, 121-130〕 There is a conjecture that any equality-constrained one-dimensional instance with ''n'' orders has at least one minimum waste solution with no more than ''n'' + 1 patterns. * The minimum stack problem: this is concerned with the sequencing of the patterns so as not to have too many partially completed orders at any time. This was an open problem until 2007, when an efficient algorithm based on dynamic programming was published.〔Maria Garcia de la Banda, P. J. Stuckey. ''Dynamic Programming to Minimize the Maximum Number of Open Stacks''. INFORMS Journal on Computing, Vol. 19, No. 4, Fall 2007, 607-617.〕 * The minimum number of knife changes problem (for the one-dimensional problem): this is concerned with sequencing and permuting the patterns so as to minimise the number of times the slitting knives have to be moved. This is a special case of the generalised travelling salesman problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cutting stock problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.